#include <cstdio>
#include <cstring>

int fac[ 20 ], fn;
long long ans;

void dfs( int p, int m, int r, int flag )
{
    int i;
    ans += ( r + m / r * r ) * 1LL * ( m / r ) / 2 * flag;
    for ( i = p; i < fn; i++ )
        dfs( i + 1, m, r * fac[ i ], -flag );
}

int a[ 400001 ], b[ 1001 ];

void gan( int p )
{
    int i = 2;
    fn = 0;
    while ( p != 1 && i * i <= p )
    {
        if ( p % i == 0 )
            fac[ fn++ ] = i;
        while ( p % i == 0 )
            p /= i;
        i++;
    }
    if ( p != 1 )
        fac[ fn++ ] = p;
}

int gcd( int a, int b )
{
    int rem;
    while ( b )
    {
        rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}

int main( )
{
    int t, n, m, cmd, x, y, p, tmp, c1, c2, i, j;
    long long l, r, ret;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d%d", &n, &m);
        memset( a, 0, sizeof( a ) );
        memset( b, 0, sizeof( b ) );
        j = 0;
        while ( m-- )
        {
            scanf("%d", &cmd);
            if ( cmd == 1 )
            {
                scanf("%d%d%d", &x, &y, &p);
                if ( x > y )
                {
                    t = x;
                    x = y;
                    y = t;
                }
                gan( p );
                ans = 0;
                dfs( 0, y, 1, 1 );
                r = ans;
                ans = 0;
                dfs( 0, x - 1, 1, 1 );
                l = ans;
                ret = r - l;
                for ( i = 0; i < j; i++ )
                    if ( b[ i ] >= x && b[ i ] <= y )
                    {
                        c1 = gcd( b[ i ], p );
                        c2 = gcd( a[ b[ i ] ], p );
                        if ( c1 != 1 && c2 == 1 )
                            ret += a[ b[ i ] ];
                        if ( c1 == 1 && c2 != 1 )
                            ret -= b[ i ];
                        if ( c1 == 1 && c2 == 1 )
                            ret += a[ b[ i ] ] - b[ i ];
                    }
                printf("%I64d\n", ret);
            }
            else
            {
                scanf("%d%d", &x, &p);
                if ( a[ x ] == 0 )
                {
                    b[ j ] = x;
                    j++;
                }
                a[ x ] = p;
            }
        }
    }
    return 0;
}
